package base.sort;

import base.utils.ArrayUitls;
import base.utils.PrintUtils;

import java.util.Arrays;

/**
 * 归并排序
 * 对此的理解为 先二分 后归并
 * https://www.runoob.com/w3cnote/merge-sort.html
 * <p>
 * https://zhuanlan.zhihu.com/p/124356219
 */
public class MergeSort implements IArraySort {

    // 交容易理解
    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2); // 是向下取整计算  5.1 = 5   , 5.9 = 5

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right)); //这里对arr进行无限二分，直到得到一个相对分散的array，然后进行归并
    }

    public int[] merge(int[] left, int[] right) {

        int[] result = new int[left.length + right.length];
        int i = 0;

        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {                                      // true , left < right ,去值left
                result[i++] = left[0];                                     //先result[i] 赋值  然后 i++ ,
                left = Arrays.copyOfRange(left, 1, left.length);    //一般从0 --> len为完整拷贝，这里相当于去除首个数据，及left[0]
            } else {
                result[i++] = right[0];                                     //赋值 较小的一个
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        //left or right 会有一个先结束，
        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }


    private static int[] mergeArr(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;

        int a =0 ,b =0;

        // 并 对两个 (已经排序)数组 ， 依据大小进行排序，这里的极限是两个length为1 数组进行比较 ,或者 left={4,};right={1,3,}
        while (a < left.length && b < right.length ){
            if (left[a] > right[b]){
                result[i] = right[b];
                b++;
            }else {
                result[i]  = left [a];
                a++;
            }
            i++;
        }

        while (left.length > a) {
            result[i]  = left [a];
            a++;
            i++;
        }

        while (right.length > b) {
            result[i] = right[b];
            b++;
            i++;
        }

//        PrintUtils.print("left="+ ArrayUitls.arr2String(left)+ ";right="+ArrayUitls.arr2String(right)+ ";result="+ArrayUitls.arr2String(result));
        return result;
    }




    /*-----------------------------------------迭代法--------------------------------------------*/

    // 归并排序（Java-迭代版）
    public static void merge_sort(int[] arr) {

        int len = arr.length;

        int[] result = new int[len];

        int block, start;

        // 原版代码的迭代次数少了一次，没有考虑到奇数列数组的情况
        for (block = 1; block < len * 2; block *= 2) {
            for (start = 0; start < len; start += 2 * block) {
                int low = start;
                int mid = (start + block) < len ? (start + block) : len;
                int high = (start + 2 * block) < len ? (start + 2 * block) : len;

                //两个块的起始下标及结束下标
                int start1 = low, end1 = mid;
                int start2 = mid, end2 = high;

                //开始对两个block进行归并排序
                while (start1 < end1 && start2 < end2) {
                    result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
                }

                while (start1 < end1) {
                    result[low++] = arr[start1++];
                }

                while (start2 < end2) {
                    result[low++] = arr[start2++];
                }

            }
            int[] temp = arr;
            arr = result;
            result = temp;
        }
        result = arr;
    }


    /*----------------------------------递归---------------------------------------------------*/

    public static void mergeSort(int[] arr) {
        int len = arr.length;
        int[] result = new int[len];
        mergeSortRecursive(arr, result, 0, len - 1);
    }

    // 归并排序（Java-递归版）
    static void mergeSortRecursive(int[] arr, int[] result, int start, int end) {
        if (start >= end) return;

        //将数组分成两份       归
        int len = end - start;
        int mid = (len / 2) + start;

        int leftStart = start, leftEnd = mid;
        int rightStart = mid + 1, rightEnd = end;

        mergeSortRecursive(arr, result, leftStart, leftEnd);
        mergeSortRecursive(arr, result, rightStart, rightEnd);


        //并
        int k = start;
        System.out.println("leftStart=" + leftStart + ";leftEnd=" + leftEnd + ";  rightStart=" + rightStart  + ";rightEnd=" + rightEnd+
                ";arr="+ ArrayUitls.arr2String(arr)+";result="+ArrayUitls.arr2String(result));

        //赋予较小的值
        while (leftStart <= leftEnd && rightStart <= rightEnd) {
            result[k++] = arr[leftStart] < arr[rightStart] ? arr[leftStart++] : arr[rightStart++];
        }

        System.out.println("leftStart="+leftStart+";leftEnd="+leftEnd+";  rightStart="+rightStart+";rightEnd="+rightEnd+";result="+ArrayUitls.arr2String(result));
        System.out.println();

        //在二分的时候存在奇数的情况，下
        while (leftStart <= leftEnd) result[k++] = arr[leftStart++];

        while (rightStart <= rightEnd) result[k++] = arr[rightStart++];

        for (k = start; k <= end; k++) arr[k] = result[k];

    }


    /*----------------------------------递归---------------------------------------------------*/

    public static void sorts(int[] arr) {
        int[] temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(arr, 0, arr.length - 1, temp);
    }

    private static void sort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            sort(arr, left, mid, temp);             //左边归并排序，使得左子序列有序
            sort(arr, mid + 1, right, temp);    //右边归并排序，使得右子序列有序
            merge(arr, left, mid, right, temp);     //将两个有序子数组合并操作
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;           //左序列指针
        int j = mid + 1;        //右序列指针
        int t = 0;              //临时数组指针

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }

        while (i <= mid) {              //将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }

        while (j <= right) {            //将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }

        t = 0;
                                        //将temp中的元素全部拷贝到原数组中
        while (left <= right) {
            arr[left++] = temp[t++];
        }
    }


}
